Search for: All records

This paper considers a two-player game where each player chooses a resource from a finite collection of options. Each resource brings a random reward. Both players have statistical information regarding the rewards of each resource. Additionally, there exists an information asymmetry where each player has knowledge of the reward realizations of different subsets of the resources. If both players choose the same resource, the reward is divided equally between them, whereas if they choose different resources, each player gains the full reward of the resource. We first implement the iterative best response algorithm to find an ϵ-approximate Nash equilibrium for this game. This method of finding a Nash equilibrium may not be desirable when players do not trust each other and place no assumptions on the incentives of the opponent. To handle this case, we solve the problem of maximizing the worst-case expected utility of the first player. The solution leads to counter-intuitive insights in certain special cases. To solve the general version of the problem, we develop an efficient algorithmic solution that combines online convex optimization and the drift-plus penalty technique.

 

This paper revisits a classical problem of slotted multiple access with success, idle, and collision events on each slot. First, results of a 2-user multiple access game are reported. The game was conducted at the University of Southern California over multiple semesters and involved competitions between studentdesigned algorithms. An algorithm called 4-State was a consistent winner. This algorithm is analyzed and shown to have an optimal expected score when competing against an independent version of itself. The structure of 4-State motivates exploration of the open question of how to minimize the expected time to capture the channel for a n-user situation. It is assumed that the system delivers perfect feedback on the number of users who transmitted at the end of each slot. An efficient algorithm is developed and conjectured to have an optimal expected capture time for all positive integers n. Optimality is proven in the special cases n ∈ {1, 2, 3, 4, 6} using a novel analytical technique that introduces virtual users with enhanced capabilities. 

This paper proves a representation theorem regarding sequences of random elements that take values in a Borel space and are measurable with respect to the sigma algebra generated by an arbitrary union of sigma algebras. This, together with a related representation theorem of Kallenberg, is used to characterize the set of multidimensional decision vectors in a discrete time stochastic control problem with measurability and causality constraints, including opportunistic scheduling problems for timevarying communication networks. A network capacity theorem for these systems is refined, without requiring an implicit and arbitrarily complex extension of the state space, by introducing two measurability assumptions and using a theory of constructible sets. An example that makes use of well known pathologies in descriptive set theory is given to show a nonmeasurable scheduling scheme can outperform all measurable scheduling schemes. 

Future generation wireless technologies are expected to serve an increasingly dense and dynamic population of users that generate short bundles of information to be transferred over the shared spectrum. This calls for new distributed and low-overhead Multiple-Access-Control (MAC) strategies to serve such dynamic demands with spectral efficiency characteristics. In this work, we address this need by identifying and developing two fundamentally different MAC paradigms: (i) congestion-based paradigm that estimates the congestion level in the system and adapts to it; and (ii) age-based paradigm that prioritizes demands based on their ages. Despite their apparent differences, we develop policies under each paradigm in a generic multi-channel access scenario that are provably throughput-optimal when they employ any asymptotically-efficient channel encoding/decoding mechanism. We also characterize the stability regions of the two designs, and investigate the conditions under which one design outperforms the other. We perform extensive simulations to validate the theoretical claims and investigate the non-asymptotic performances of our designs. 

This paper considers online optimization of a renewal-reward system. A controller performs a sequence of tasks back-to-back. Each task has a random vector of parameters, called the task type vector, that affects the task processing options and also affects the resulting reward and time duration of the task. The probability distribution for the task type vector is unknown and the controller must learn to make efficient decisions so that time-average reward converges to optimality. Prior work on such renewal optimization problems leaves open the question of optimal convergence time. This paper develops an algorithm with an optimality gap that decays like O(1/√k), where k is the number of tasks processed. The same algorithm is shown to have faster O(log(k)/k) performance when the system satisfies a strong concavity property. The proposed algorithm uses an auxiliary variable that is updated according to a classic Robbins-Monro iteration. It makes online scheduling decisions at the start of each renewal frame based on this variable and the observed task type. A matching converse is obtained for the strongly concave case by constructing an example system for which all algorithms have performance at best Ω(log(k)/k). A matching Ω(1/√k) converse is also shown for the general case without strong concavity. 

With the adoption of 5G wireless technology and the Internet-of-Things (IoT) networking, there is a growing interest in serving a dense population of low-complexity devices over shared wireless uplink channels. Different from the traditional scenario of persistent users, in these new networks each user is expected to generate only small bundles of information intermittently. The highly dynamic nature of such demand and the typically low-complexity nature of the user devices calls for a new MAC paradigm that is geared for low-overhead and distributed operation of dynamic users.In this work, we address this need by developing a generic MAC mechanism for estimating the number and coordinating the activation of dynamic users for efficient utilization of the time-frequency resources with minimal public feedback from the common receiver. We fully characterize the throughput and delay performance of our design under a basic threshold-based multi-channel capacity condition, which allows for the use of different channel utilization schemes. Moreover, we consider the Successive-Interference-Cancellation (SIC) Multi-Channel MAC scheme as a specific choice in order to demonstrate the performance of our design for a spectrally-efficient (albeit idealized) scheme. Under the SIC encoding/decoding scheme, we prove that our low-overhead distributed MAC can support maximum throughput, which establishes the efficiency of our design. Under SIC, we also demonstrate how the basic threshold-based success model can be relaxed to be adapted to the performance of a non-ideal success model. 

This paper considers online optimization of a renewal-reward system. A controller performs a sequence of tasks back-to-back. Each task has a random vector of parameters, called the \emph{task type vector}, that affects the task processing options and also affects the resulting reward and time duration of the task. The probability distribution for the task type vector is unknown and the controller must learn to make efficient decisions so that time average reward converges to optimality. Prior work on such renewal optimization problems leaves open the question of optimal convergence time. This paper develops an algorithm with an optimality gap that decays like $O(1/\sqrt{k})$, where $k$ is the number of tasks processed. The same algorithm is shown to have faster $O(\log(k)/k)$ performance when the system satisfies a strong concavity property. The proposed algorithm uses an auxiliary variable that is updated according to a classic Robbins-Monro iteration. It makes online scheduling decisions at the start of each renewal frame based on this variable and on the observed task type. A matching converse is obtained for the strongly concave case by constructing an example system for which all algorithms have performance at best $\Omega(\log(k)/k)$. A matching $\Omega(1/\sqrt{k})$ converse is also shown for the general case without strong concavity. 

This paper presents a network layer model for a wireless multiple access system with both persistent and nonpersistent users. There is a single access point with multiple identical channels. Each user who wants to send a file first scans a subset of the channels to find one that is idle. If at least one idle channel is found, the user transmits a file over that channel. If no idle channel is found, a persistent user will repeat the access attempt at a later time, while a nonpersistent user will leave. This is a useful mathematical model for situations where a group of persistent users stay near an access point for an extended period of time while nonpersistent users come and go. Users have heterogeneous activity behavior, file upload rates, and service durations. The system is a complex multi-dimensional Markov chain. The steady state probabilities are found by exploiting a latent reversibility property and leveraging a discrete Fourier transform. This enables simple expressions for throughput and blocking probability. 

This paper considers online convex optimization (OCO) problems where decisions are constrained by available energy resources. A key scenario is optimal power control for an energy harvesting device with a finite capacity battery. The goal is to minimize a time-average loss function while keeping the used energy less than what is available. In this setup, the distribution of the randomly arriving harvestable energy (which is assumed to be i.i.d.) is unknown, the current loss function is unknown, and the controller is only informed by the history of past observations. A prior algorithm is known to achieve $O(\sqrtT )$ regret by using a battery with an $O(\sqrtT )$ capacity. This paper develops a new algorithm that maintains this asymptotic trade-off with the number of time steps T while improving dependency on the dimension of the decision vector from $O(\sqrtn )$ to $O(\sqrtłog(n) )$. The proposed algorithm introduces a separation of the decision vector into amplitude and direction components. It uses two distinct types of Bregman divergence, together with energy queue information, to make decisions for each component.